package E_2024;

import java.util.Arrays;

/*
    给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。
输入描述:
    输入的第一行包含2个整数n, m(1 <= n, m <= 10)，表示一个n行m列的矩阵，下面有n行，每行有m个整数，同一行中，每2个数字之间有1个空格，最后一个数字后面没有空格，所有的数字的在[-1000, 1000]之间。
输出描述:
    输出一行一个数字，表示选出的和最大子矩阵内所有的数字和。
示例1   输入输出示例仅供调试，后台判题数据一般不包含示例
输入
    3 4
    -3 5 -1 5
    2 4 -2 4
    -1 3 -1 3
输出
    20
 */
public class E_100_30 {
    public static void main(String[] args) {
        System.out.println(ans(new int[][]{{-3,5,-1,5},{2,4,-2,4},{-1,3,-1,3}}));
        System.out.println("---");
        System.out.println(ans(new int[][]{{-3,-1,3,-9},{1,4,-2,1},{-4,3,-2,1}}));
        System.out.println("---");
        System.out.println(ans(new int[][]{{5,-3,-1,5},{1,4,-2,4},{-7,3,-1,3}}));
    }

    /**
     * 在一维数组中，寻找最大和区间时通常将当前值与当前下标所有值的和比较，取最大值
     * 例：[9，2，-6，5]  进行累加比较操作后得到 [9,11,5,10], 其中最大值为 11， 即 最大和区间为 [9,2]
     *    [-1,-2,9,-1]  进行累加比较操作后得到 [-1,-2,9,8], 其中最大值为9，即最大区间为 [9]
     * 在二维数组中寻找最大二维区间时也可以使用该方法
     *    将所有可能的行数组合压缩到一个一维数组中
     *    例：3*4 数组的可能性有 1，1+2，1+2+3，2，2+3，3 共6种可能，因为二维区间必须相邻，不可能1+3行，这两行无法组合成一个连续的二维数组
     */
    public static int ans(int[][] arr){
        for (int[] ints : arr) {
            System.out.println(Arrays.toString(ints));
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j] += arr[i-1][j];
            }
        }
        System.out.println("====");
        for (int[] ints : arr) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("====");
        int maximum = Integer.MIN_VALUE;
        // 最大二维数组的起始行
        for (int i = 0; i < arr.length; i++) {
            // 终止行
            for (int j = i; j < arr.length; j++) {
                // 一维数组记录当前二维数组的压缩值
                int[] result = new int[arr[0].length];
                for (int k = 0; k < arr[0].length; k++) {
                    // 当起始行是第一行时，所有可能就是中间数组temp的各行
                    if (i == 0)
                        result[k] = arr[j][k];
                    // 当起始行不是第一行时，就是中间数组减去中间数组起始行上一行的值
                    else
                        result[k] = arr[j][k] - arr[i-1][k];
                }
                System.out.println(Arrays.toString(result));
                maximum = Math.max(maximum,maxSubsequence(result));
            }
        }
        return maximum;
    }
    public static int maxSubsequence(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int[] maxSub = new int[array.length];
        maxSub[0] = array[0];

        for (int i = 1; i < array.length; i++) {
            maxSub[i] = (maxSub[i-1] > 0) ? (maxSub[i-1] + array[i]) : array[i];
            if (max < maxSub[i]) {
                max = maxSub[i];
            }
        }
        return max;
    }

}
